package com.fr.lintcode;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月9日
*时间：下午3:56:59
*/
public class Q131ii {
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
        ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
        if (buildings == null || buildings.length <= 0) {
            return rs;
        }
        Map<Integer, List<Line>> map = new HashMap<>();
        Set<Integer> height = new HashSet<>();
        for (int[] a : buildings) {
            List<Line> list = map.get(a[2]);
            if (list == null) {
                list = new ArrayList<>();
                list.add(new Line(a[0], a[1]));
                map.put(a[2], list);
            } else {
                list.add(new Line(a[0], a[1]));
            }
            height.add(a[2]);
        }
        List<Integer> h = new ArrayList<>(height);
        Collections.sort(h, Collections.reverseOrder());
        List<Line> exclude = new ArrayList<>();
        for (int i : h) {
            List<Line> l = map.get(i);
            l = merge(l);
            l = exclude(l, exclude);
            exclude.addAll(l);
        }
        return rs;
    }

    // TODO 排除
    private List<Line> exclude(List<Line> l, List<Line> exclude) {
        exclude = merge(exclude);
        for (Line a : l) {
            for (Line b : exclude) {
                if (a.begin >= b.end) {

                } else {

                }
            }
        }
        return null;
    }

    private List<Line> merge(List<Line> l) {
        Collections.sort(l);
        Line tmp = l.get(0);
        List<Line> rs = new ArrayList<>();
        for (int i = 1; i < l.size(); i++) {
            Line a = l.get(i);
            if (tmp.end < a.begin) {
                rs.add(tmp);
                tmp = a;
            } else {
                tmp.end = Math.max(tmp.end, a.end);
            }
        }
        return rs;
    }

    class Line implements Comparable<Line> {
        int begin;
        int end;

        Line(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }

        @Override
        public int compareTo(Line o) {
            return this.begin - o.begin;
        }
    }

    @Test
    public void testA() throws IOException {
        // int[][] buildings = { { 1, 3, 3 }, { 2, 4, 4 }, { 5, 6, 1 } };
        // int[][] buildings = { { 1, 10, 3 }, { 2, 5, 8 }, { 7, 9, 8 } };
        File f = new File("C:\\Users\\Hunteron\\Downloads\\15.in");
        FileReader fr = new FileReader(f);
        @SuppressWarnings("resource")
        BufferedReader br = new BufferedReader(fr);
        String line = br.readLine();
        String[] s = line.split("},");
        int[][] buildings = new int[s.length][3];
        for (int i = 0; i < s.length; i++) {
            String n[] = s[i].split(",");
            if (n.length == 3) {
                buildings[i][0] = Integer.parseInt(n[0]);
                buildings[i][1] = Integer.parseInt(n[1]);
                buildings[i][2] = Integer.parseInt(n[2]);
            }
        }
        long begin = System.currentTimeMillis();
        ArrayList<ArrayList<Integer>> rs = buildingOutline(buildings);
        System.out.println(System.currentTimeMillis() - begin);
        System.out.println(rs);
    }
}
